package LeetCode;

public class LC_312_BurstBalloons {

    public static void main(String[] args) {

    }

    public class Solution {
        public int maxCoins(int[] nums) {
            int n = nums.length;
            int[] newNum = new int[n + 2];
            newNum[0] = 1;
            newNum[n + 1] = 1;
            System.arraycopy(nums, 0, newNum, 1, n);
            int[][] memo = new int[n + 2][n + 2];
            return dfs(newNum, memo, 0, n + 1);
        }

        int dfs(int[] nums, int[][] memo, int left, int right) {
            if (right - left <= 1) return 0;
            if (memo[left][right] != 0) return memo[left][right];
            int ans = 0;
            for (int i = left + 1; i < right; i++)
                ans = Math.max(ans, dfs(nums, memo, left, i) + dfs(nums, memo, i, right) + nums[left] * nums[i] * nums[right]);
            memo[left][right] = ans;
            return ans;
        }

    }
}
